package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class 单词拆分2 {
    List<String> res = new ArrayList<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        StringBuilder path=new StringBuilder();
        StringBuilder sb=new StringBuilder();
        backTracking(s,s,wordDict,path,sb);
        return res;
    }

    private void backTracking(String ss,String s, List<String> wordDict, StringBuilder  path, StringBuilder sb) {
        if (sb.toString().equals(ss)){
            path.deleteCharAt(path.length()-1);
            res.add(new String(path));
        }
        for (String string : wordDict) {
            if (s.startsWith(string) ){
                StringBuilder path2 = new StringBuilder(path);
                StringBuilder sb2 = new StringBuilder(sb);
                path2.append(string+" ");
                sb2.append(string);
                backTracking(ss,s.substring(string.length()), wordDict, path2, sb2);
            }
        }
    }
}